package 蓝桥真题;

import java.math.BigInteger;

public class RSA解密 {
	
	   static long gcd(long a,long b){
		     return b>0?gcd(b,a%b):a;
	   }
	   static long qmi(BigInteger a,long k,BigInteger m){
		      BigInteger res=new BigInteger("1");
		      while(k>0){
		    	  if((k&1)==1)res=res.multiply(a).mod(m);
		    	  k=k>>1;
		    	  a=a.multiply(a).mod(m);
		      }
		      return res.longValue();
	   }
       public static void main(String[] args) {
//    	      long n=1001733993063167141L;
//		      for(long i=2;i<=n/i;i++)
//		    	  if(n%i==0){
//		    		  System.out.println(i);
//		    		  n/=i;
//		    	  }
//		      System.out.print(n);
    	      System.out.print(qmi(new BigInteger("20190324"),823816093931522017L,new BigInteger("1001733993063167141")));
		      
	}
}
